We describe a general-purpose method for finding high-quality solutions tohard optimization problems, inspired by self-organized critical models ofco-evolution such as the Bak-Sneppen model. The method, called ExtremalOptimization, successively eliminates extremely undesirable components ofsub-optimal solutions, rather than ``breeding'' better components. In contrastto Genetic Algorithms which operate on an entire ``gene-pool'' of possiblesolutions, Extremal Optimization improves on a single candidate solution bytreating each of its components as species co-evolving according to Darwinianprinciples. Unlike Simulated Annealing, its non-equilibrium approach effects analgorithm requiring few parameters to tune. With only one adjustable parameter,its performance proves competitive with, and often superior to, more elaboratestochastic optimization procedures. We demonstrate it here on two classic hardoptimization problems: graph partitioning and the traveling salesman problem.
展开▼
